package tree.HuffmanTree;

import java.io.*;
import java.util.*;

public class HuffmanCode {
	public static void main(String[] args) {
        /*====对字符串压缩与解压======================
        String str = "i like like like java do you like java";
        byte[] contentBytes = str.getBytes();
        byte[] huffmanCodeBytes = haffmanZip(contentBytes);
        System.out.println("huffmanCodeBytes :"+ Arrays.toString(huffmanCodeBytes));
        byte[] source = decode(huffmancodes,huffmanCodeBytes);
        System.out.println("原来的字符串："+ new String(source));
        ============================================*/

		//*====对文件压缩与解压========================
		String srcFile = "C://Users//chenyuan//Desktop//src.txt";
		String dstFile = "C://Users//chenyuan//Desktop//dst.zip";

		zipFile(srcFile, dstFile);
		System.out.println("压缩文件");

		String zipFile = "C://Users//chenyuan//Desktop//dst.zip";
		String dstFile2 = "C://Users//chenyuan//Desktop//src1111.txt";
		unZipFile(zipFile, dstFile2);
		System.out.println("解压");

		//==========================================*/
	}

	//====将一个文件进行压缩======================================

	/**
	 * @param srcFile 需要压缩的文件的路径
	 * @param dstFlie 压缩后保存的路径
	 */
	public static void zipFile(String srcFile, String dstFlie) {
		//创建输出流
		OutputStream os = null;
		ObjectOutputStream oos = null;
		//创建文件的输入流
		FileInputStream is = null;
		try {
			is = new FileInputStream(srcFile);
			//创建一个和源文件大小一样的 byte 数组，读取数据
			byte[] b = new byte[is.available()];
			//读取文件
			is.read(b);
			//直接对源文件压缩
			byte[] huffmanBytes = haffmanZip(b);
			//创建一个文件的输出流，存放压缩文件
			os = new FileOutputStream(dstFlie);
			//创建一个和文件输出流关联的 ObjectOutputStream
			oos = new ObjectOutputStream(os);
			//先把 huffmanBytes 写入压缩文件
			oos.writeObject(huffmanBytes);

			//以对象流的方式写入 哈夫曼编码 ，是为了后面解压时使用
			//一定要把 哈夫曼编码 一起写入压缩文件，在解压时需要相同的编码
			oos.writeObject(huffmancodes);

		} catch (Exception e) {
			System.out.println(e.getMessage());
		} finally {
			try {
				is.close();
				oos.close();
				os.close();
			} catch (IOException e) {
				System.out.println(e.getMessage());
			}
		}


	}
	//==========================================================

	//====将一个文件进行解压======================================

	/**
	 * @param zipFile 需要解压的文件
	 * @param dstFile 解压完后路径
	 */
	public static void unZipFile(String zipFile, String dstFile) {
		//定义文件的输入流
		InputStream is = null;
		//与输入流有关的 对象流
		ObjectInputStream ois = null;
		//定义文件的输出流
		OutputStream os = null;

		try {
			//创建文件输入流
			is = new FileInputStream(zipFile);
			//创建一个和 is 关联的 对象流
			ois = new ObjectInputStream(is);
			//读取 byte 数组 -> huffmanBytes
			byte[] huffmanBytes = (byte[]) ois.readObject();
			//读取哈夫曼编码表
			Map<Byte, String> huffmancodes2 = (Map<Byte, String>) ois.readObject();
			//解码
			byte[] bytes = decode(huffmancodes2, huffmanBytes);
			//将 bytes 数组写入目标文件
			os = new FileOutputStream(dstFile);
			//写数据到文件中
			os.write(bytes);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				os.close();
				ois.close();
				is.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}


	}


	//==========================================================


	//======数据解压===========================================
	//   1. 把 huffmanCodeBytes 转成 哈夫曼编码对应的二进制
	//   2. 把 二进制字符串，对照哈夫曼编码，转换成字符串

	/**
	 * 把 一个 byte 转成 一个二进制字符串
	 *
	 * @param b    待转换的字节
	 * @param flag 标识是否需要补高位，若为 true 需要；false 不需要
	 * @return 返回 byte 对应的 二进制补码
	 */
	private static String byteToString(byte b, boolean flag, int bit) {
		//使用一个编码保存 b

		int temp = b;
		//根据所传递的位数进行截取
		//如果是无符号数，那么值如果太小必然无法得到8位二进制，因为我们进行或运算高位补0，最后在截取,并不会影响最终结果
		int x = 1 << bit;
		temp |= x;//进行或运算，补高位
		String byteStr = Integer.toBinaryString(temp);
		//因为我们压缩式是取8位进行压缩，所以其每个sbyte
		//大于Tmax=(2^w-1)-1,不会小于Tmin=-2^w-1;
		//但因为Convert.Tostirng()转换为16位二进制或更高
		//byteStr.Length - bit=所需要截取的下标位置
		return byteStr.substring(byteStr.length() - bit);
	}

	/**
	 * 对压缩数据解码
	 *
	 * @param huffmancodes 哈夫曼编码
	 * @param huffmanBytes 哈夫曼编码处理后的字节数组
	 * @return
	 */
	private static byte[] decode(Map<Byte, String> huffmancodes, byte[] huffmanBytes) {
		// 1. 先得到 huffmanBytes 对应的二进制的字符串
		StringBuilder stringBuilder = new StringBuilder();
		// 2. 将 byte 数组转成二进制字符串
		for (int i = 0; i < huffmanBytes.length; i++) {
			byte b = huffmanBytes[i];
			boolean flag = (i == huffmanBytes.length - 1);
			stringBuilder.append(byteToString(b, !flag, 8));
		}

		// 把字符串按照哈夫曼编码表 进行解码
		// 要把 哈夫曼编码 键值调转
		Map<String, Byte> map = new HashMap<>();
		for (Map.Entry<Byte, String> entry : huffmancodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}

		//创建集合，存放 byte
		List<Byte> list = new ArrayList<>();
		//扫描 StringBudlier
		for (int i = 0; i < stringBuilder.length(); ) {
			int count = 1;//计数器
			boolean flag = true;
			Byte b = null;

			while (flag) {
				//取出每个 byte
				String key = stringBuilder.substring(i, i + count);
				b = map.get(key);
				if (b == null) {
					//没有匹配到
					count++;
				} else {
					//匹配到
					flag = false;
				}
			}

			list.add(b);
			i += count;//i直接到下一位
		}

		// for 循环结束后，list中存放了所有的字符
		byte[] b = new byte[list.size()];
		for (int i = 0; i < b.length; i++) {
			b[i] = list.get(i);
		}
		return b;
	}
	//=========================================================

	//===压缩数据，封装所有操作，便于调用=========================
	private static byte[] haffmanZip(byte[] contentBytes) {

		//生成 列表
		List<Node1> nodes = getNodes(contentBytes);
		//创建哈夫曼树
		Node1 root = createHuffmanTree2(nodes);
		//生成对应的 哈夫曼编码
		Map<Byte, String> huffmancodes = getCode(root);
		//根据的哈夫曼树编码，得到压缩后的哈夫曼字节数组
		byte[] huffmanCodeBytes = zipString(contentBytes, huffmancodes);
		return huffmanCodeBytes;
	}

	/**
	 * @param bytes        原始字符串对应的 数组
	 * @param huffmancodes 生成的哈夫曼编码
	 * @return 返回哈夫曼编码处理后的 数组
	 */
	//将一个字符串，对应的 Byte 数组，通过生成的 哈夫曼编码表 ，返回一个处理后的一个 byte 数组
	private static byte[] zipString(byte[] bytes, Map<Byte, String> huffmancodes) {
		// 1. 先利用哈夫曼编码表，把 byte 转成 哈夫曼编码对应的字符串
		StringBuilder stringBuilder = new StringBuilder();
		// 遍历 byte 数组
		for (byte b : bytes) {
			stringBuilder.append(huffmancodes.get(b));
		}

		//System.out.println("stringBuilder :"+stringBuilder.toString());

		//将 stringBuilder 对应的字符串，转成 byte 数组
		//统计 stringBuilder 对应的字符串长度
		int length;
		if (stringBuilder.length() % 8 == 0) {
			length = stringBuilder.length() / 8;
		} else {
			length = stringBuilder.length() / 8 + 1;
		}
		//创建 huffmanCodeBytes,每八位对应一个字节
		byte[] huffmanCodeBytes = new byte[length];
		int index = 0;//定义一个计数器，记录是第几个 byte

		for (int i = 0; i < stringBuilder.length(); i += 8) {
			String strByte;
			//防止越界
			if (i + 8 > stringBuilder.length()) {
				//不足 8 位
				//从 i 开始取 到最后
				strByte = stringBuilder.substring(i);
			} else {
				//从 i 开始取 8 位
				strByte = stringBuilder.substring(i, i + 8);
			}

			//将 strByte 转成一个 byte 放入到 huffmanCodeBytes
			huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
			index++;
		}


		return huffmanCodeBytes;
	}
	//==============================================================

	//生成 哈夫曼树 对应的 哈夫曼编码
	//   1. 把哈夫曼编码表放在 Map<Byte, String>中
	static Map<Byte, String> huffmancodes = new HashMap<>();
	//   2.在生成 哈夫曼编码表时，需要拼接路径，定义一个 StringBuilder 存储某个叶子节点路径
	static StringBuilder stringBuilder = new StringBuilder();

	//为方便调用，重载 getCode
	private static Map<Byte, String> getCode(Node1 root) {
		if (root == null) {
			return null;
		}
		getCode(root, "", stringBuilder);
		return huffmancodes;
	}

	/**
	 * 把传入的 node节点的所有叶子节点的哈夫曼编码得到，并放入到 huffmancodes
	 *
	 * @param node          传入的节点
	 * @param code          路径，左子节点为 0，右子节点为 1
	 * @param stringBuilder 是用于拼接路径
	 */
	private static void getCode(Node1 node, String code, StringBuilder stringBuilder) {
		StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
		//将 code 加入到 stringBuilder2
		stringBuilder2.append(code);
		if (node != null) {
			//若为空，不处理
			//判断是否时叶子节点
			if (node.date == null) {
				//非叶子节点
				//递归处理
				//向左
				getCode(node.left, "0", stringBuilder2);
				//向右
				getCode(node.right, "1", stringBuilder2);
			} else {
				//叶子节点
				//表示找到了某个叶子节点
				huffmancodes.put(node.date, stringBuilder2.toString());
			}

		}
	}

	//前序遍历
	private static void preOrder(Node1 root) {
		if (root != null) {
			root.preOrder();
		} else {
			System.out.println("树为空");
		}
	}

	//
	private static List<Node1> getNodes(byte[] bytes) {
		// 1. 创建一个 ArrayList
		List<Node1> nodes = new ArrayList<>();

		// 2. 存储每个byte 出现的次数 -> map
		Map<Byte, Integer> counts = new HashMap<>();
		for (byte b : bytes) {
			Integer count = counts.get(b);
			if (count == null) {
				//若成立，map中没有此数据
				counts.put(b, 1);
			} else {
				counts.put(b, count + 1);
			}
		}
		// 3. 把每个键值对转换成一个 Node 对象，并加入到 nodes 集合
		// map.entrySet() 是把 Map 中的键值对映射关系变为集合，其数据类型为 Map.Entry
		for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
			nodes.add(new Node1(entry.getKey(), entry.getValue()));
		}

		return nodes;
	}

	// 4. 通过 List 创建对应的哈夫曼树
	private static Node1 createHuffmanTree2(List<Node1> nodes) {
		while (nodes.size() > 1) {
			//排序，从小到大
			Collections.sort(nodes);
			//取出第一个最小的二叉树
			Node1 leftNode = nodes.get(0);
			Node1 rigthNode = nodes.get(1);
			//创建一个新的二叉树,新的二叉树的根节点没有 数据 只有 权值
			Node1 parent = new Node1(null, leftNode.weight + rigthNode.weight);
			parent.left = leftNode;
			parent.right = rigthNode;

			//将处理过的两个子树，用nodes删除
			nodes.remove(leftNode);
			nodes.remove(rigthNode);

			//把新的二叉树加入到 nodes
			nodes.add(parent);
		}

		//nodes 最后的节点就是根节点
		return nodes.get(0);
	}


}

//创建 Node ，带数据和权值
class Node1 implements Comparable<Node1> {
	Byte date;//存放的数据对应的 Ascii码
	int weight;//权值
	Node1 left;
	Node1 right;

	public Node1(Byte date, int weight) {
		this.date = date;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node1 o) {
		return this.weight - o.weight;
	}

	@Override
	public String toString() {
		return "Node1{" +
				"date=" + date +
				", weight=" + weight +
				'}';
	}

	//前序遍历
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}
		if (this.right != null) {
			this.right.preOrder();
		}
	}
}
